﻿using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace g4
{
    /// <summary>
    /// 网格平面切割类：使用平面切割网格，移除平面正侧（(p-o)·n > 0）的部分
    /// 可返回切割产生的边界环，支持填充切割后形成的孔洞
    /// 
    /// 算法流程：
    ///    1) 查找所有与平面相交的边
    ///    2) 在相交点处分割边
    ///    3) 删除平面正侧的所有顶点
    ///    4)（可选）折叠切割边界上的退化边
    ///    5) 查找通过有效边界边（分割产生的边或平面上的边）形成的环
    /// 
    /// 注意：
    ///    若切割与网格中的孔洞相交，可能无法正确生成边界环
    ///    对于平面上的退化三角形（所有顶点到平面距离小于容差），可选择删除，但会增加边界边追踪的复杂度
    /// </summary>
    public class MeshPlaneCut
    {
        // 输入参数

        /// <summary>
        /// 待切割的目标网格
        /// </summary>
        public DMesh3 Mesh;

        /// <summary>
        /// 切割平面的原点
        /// </summary>
        public Vector3d PlaneOrigin;

        /// <summary>
        /// 切割平面的法向量（正方向为要移除的一侧）
        /// </summary>
        public Vector3d PlaneNormal;

        /// <summary>
        /// 是否折叠切割边界上的退化边
        /// 平面切割可能在边界产生极短边，下游操作（如孔洞填充）可能因此出错，开启此选项可提前处理
        /// </summary>
        public bool CollapseDegenerateEdgesOnCut = true;

        /// <summary>
        /// 退化边的容差（小于此长度的边被视为退化边）
        /// </summary>
        public double DegenerateEdgeTol = MathUtil.ZeroTolerancef;

        /// <summary>
        /// 若不为空，仅对该集合中的面进行切割（限制切割范围）
        /// </summary>
        public MeshFaceSelection CutFaceSet = null;

        // 输出结果

        /// <summary>
        /// 切割产生的闭合边界环列表
        /// </summary>
        public List<EdgeLoop> CutLoops;

        /// <summary>
        /// 切割产生的开放边界跨度列表
        /// </summary>
        public List<EdgeSpan> CutSpans;

        /// <summary>
        /// 标记切割边界环计算是否失败（如与网格孔洞相交）
        /// </summary>
        public bool CutLoopsFailed = false;

        /// <summary>
        /// 标记是否在切割中发现开放跨度
        /// </summary>
        public bool FoundOpenSpans = false;

        /// <summary>
        /// 每个边界环填充后产生的三角形数组列表
        /// </summary>
        public List<int[]> LoopFillTriangles;


        /// <summary>
        /// 构造函数：初始化网格平面切割器
        /// </summary>
        /// <param name="mesh">目标网格</param>
        /// <param name="origin">切割平面的原点</param>
        /// <param name="normal">切割平面的法向量</param>
        public MeshPlaneCut(DMesh3 mesh, Vector3d origin, Vector3d normal)
        {
            Mesh = mesh;
            PlaneOrigin = origin;
            PlaneNormal = normal;
        }


        /// <summary>
        /// 验证操作的合法性（当前未实现具体验证逻辑）
        /// </summary>
        /// <returns>验证状态（始终返回Ok）</returns>
        public virtual ValidationStatus Validate()
        {
            // [待实现] 可添加平面参数有效性、网格状态等检查
            return ValidationStatus.Ok;
        }


        /// <summary>
        /// 执行平面切割操作：分割相交边、删除平面正侧部分、提取边界环
        /// </summary>
        /// <returns>操作是否成功</returns>
        public virtual bool Cut()
        {
            double invalidDist = double.MinValue; // 无效顶点的距离标记

            // 若限制切割范围，预计算相关边和顶点集合
            MeshEdgeSelection cutEdgeSet = null;
            MeshVertexSelection cutVertexSet = null;
            if (CutFaceSet != null)
            {
                cutEdgeSet = new MeshEdgeSelection(Mesh, CutFaceSet); // 切割范围内的边
                cutVertexSet = new MeshVertexSelection(Mesh, cutEdgeSet); // 切割范围内的顶点
            }

            // 计算每个顶点到平面的有向距离（符号表示在平面的哪一侧）
            int maxVid = Mesh.MaxVertexID;
            double[] signs = new double[maxVid];
            gParallel.ForEach(Interval1i.Range(maxVid), (vid) => {
                if (Mesh.IsVertex(vid))
                {
                    Vector3d v = Mesh.GetVertex(vid);
                    // 有向距离 = (顶点 - 平面原点) · 平面法向量
                    signs[vid] = (v - PlaneOrigin).Dot(PlaneNormal);
                }
                else
                {
                    signs[vid] = invalidDist; // 无效顶点标记
                }
            });

            // 收集特殊边和顶点
            HashSet<int> zeroEdges = new HashSet<int>(); // 完全在平面上的边（两端点到平面距离为0）
            HashSet<int> zeroVertices = new HashSet<int>(); // 在平面上的顶点（距离为0）
            HashSet<int> onCutEdges = new HashSet<int>(); // 切割产生的边

            // 处理边分割的临时集合
            int maxEid = Mesh.MaxEdgeID;
            HashSet<int> newEdges = new HashSet<int>(); // 新创建的边

            // 确定要处理的边范围（全部边或切割范围内的边）
            IEnumerable<int> edgeItr = Interval1i.Range(maxEid);
            if (cutEdgeSet != null)
                edgeItr = cutEdgeSet;

            // 遍历边，切割与平面相交的边
            foreach (int eid in edgeItr)
            {
                if (!Mesh.IsEdge(eid))
                    continue;
                // 跳过新创建的边（避免重复处理）
                if (eid >= maxEid || newEdges.Contains(eid))
                    continue;

                Index2i ev = Mesh.GetEdgeV(eid);
                double f0 = signs[ev.a]; // 边的起点到平面的距离
                double f1 = signs[ev.b]; // 边的终点到平面的距离

                // 检查顶点是否在平面上（距离小于极小值）
                int n0 = (Math.Abs(f0) < MathUtil.Epsilon) ? 1 : 0;
                int n1 = (Math.Abs(f1) < MathUtil.Epsilon) ? 1 : 0;
                if (n0 + n1 > 0)
                {
                    if (n0 + n1 == 2)
                    {
                        zeroEdges.Add(eid); // 整条边在平面上
                    }
                    else
                    {
                        // 只有一个顶点在平面上
                        zeroVertices.Add((n0 == 1) ? ev[0] : ev[1]);
                    }
                    continue;
                }

                // 边的两端在平面同侧（无交点），跳过
                if (f0 * f1 > 0)
                    continue;

                // 分割边（在交点处创建新顶点）
                DMesh3.EdgeSplitInfo splitInfo;
                MeshResult result = Mesh.SplitEdge(eid, out splitInfo);
                if (result != MeshResult.Ok)
                {
                    throw new Exception("MeshPlaneCut.Cut: 边分割失败");
                }

                // 计算分割点的精确位置（在平面上）
                double t = f0 / (f0 - f1); // 插值参数（0到1之间）
                Vector3d newPos = (1 - t) * Mesh.GetVertex(ev.a) + t * Mesh.GetVertex(ev.b);
                Mesh.SetVertex(splitInfo.vNew, newPos); // 更新新顶点位置

                // 记录新创建的边，标记切割边
                newEdges.Add(splitInfo.eNewBN);
                newEdges.Add(splitInfo.eNewCN);
                onCutEdges.Add(splitInfo.eNewCN);
                if (splitInfo.eNewDN != DMesh3.InvalidID)
                {
                    newEdges.Add(splitInfo.eNewDN);
                    onCutEdges.Add(splitInfo.eNewDN);
                }
            }

            // 删除平面正侧的顶点（及其关联的三角形和边）
            IEnumerable<int> vertexSet = Interval1i.Range(maxVid);
            if (cutVertexSet != null)
                vertexSet = cutVertexSet;
            foreach (int vid in vertexSet)
            {
                // 仅删除在平面正侧且有效的顶点
                if (signs[vid] > 0 && Mesh.IsVertex(vid))
                    Mesh.RemoveVertex(vid, true, false); // 移除顶点，删除关联元素，不清理孤立顶点
            }

            // 折叠切割边界上的退化边（若启用）
            if (CollapseDegenerateEdgesOnCut)
            {
                collapse_degenerate_edges(onCutEdges, zeroEdges);
            }

            // 提取切割产生的边界环和跨度
            try
            {
                // 过滤函数：仅考虑切割产生的边或平面上的边
                Func<int, bool> cutEdgeFilterF = (eid) => {
                    return onCutEdges.Contains(eid) || zeroEdges.Contains(eid);
                };

                // 计算边界环和跨度
                MeshBoundaryLoops loops = new MeshBoundaryLoops(Mesh, false);
                loops.EdgeFilterF = cutEdgeFilterF;
                loops.Compute();

                CutLoops = loops.Loops;
                CutSpans = loops.Spans;
                CutLoopsFailed = false;
                FoundOpenSpans = CutSpans.Count > 0; // 标记是否有开放跨度
            }
            catch
            {
                // 提取失败时初始化空集合
                CutLoops = new List<EdgeLoop>();
                CutLoopsFailed = true;
            }

            return true;
        }


        /// <summary>
        /// 折叠切割边界上的退化边（长度小于容差的边）
        /// </summary>
        /// <param name="onCutEdges">切割产生的边</param>
        /// <param name="zeroEdges">平面上的边</param>
        protected void collapse_degenerate_edges(HashSet<int> onCutEdges, HashSet<int> zeroEdges)
        {
            HashSet<int>[] edgeSets = new HashSet<int>[2] { onCutEdges, zeroEdges };
            double tolSquared = DegenerateEdgeTol * DegenerateEdgeTol; // 容差的平方（避免开方）
            Vector3d a = Vector3d.Zero, b = Vector3d.Zero;
            int collapsedCount;

            // 循环折叠，直到没有更多退化边（可能需要多次迭代，因折叠可能产生新的退化边）
            do
            {
                collapsedCount = 0;
                foreach (var edgeSet in edgeSets)
                {
                    foreach (int eid in edgeSet)
                    {
                        if (!Mesh.IsEdge(eid))
                            continue;

                        // 检查边的长度
                        Mesh.GetEdgeV(eid, ref a, ref b);
                        if (a.DistanceSquared(b) > tolSquared)
                            continue;

                        // 折叠边（合并两个顶点）
                        Index2i ev = Mesh.GetEdgeV(eid);
                        DMesh3.EdgeCollapseInfo collapseInfo;
                        MeshResult result = Mesh.CollapseEdge(ev.a, ev.b, out collapseInfo);
                        if (result == MeshResult.Ok)
                            collapsedCount++;
                    }
                }
            } while (collapsedCount != 0);
        }


        /// <summary>
        /// 快速填充切割产生的孔洞（如需更优结果，可自行处理CutLoops）
        /// </summary>
        /// <param name="constantGroupID">填充三角形的组ID（-1表示自动分配）</param>
        /// <returns>是否所有孔洞都填充成功</returns>
        public bool FillHoles(int constantGroupID = -1)
        {
            bool allOk = true;
            LoopFillTriangles = new List<int[]>(CutLoops.Count);

            foreach (EdgeLoop loop in CutLoops)
            {
                SimpleHoleFiller filler = new SimpleHoleFiller(Mesh, loop);
                int groupID = (constantGroupID >= 0) ? constantGroupID : Mesh.AllocateTriangleGroup();
                if (filler.Fill(groupID))
                {
                    LoopFillTriangles.Add(filler.NewTriangles);
                }
                else
                {
                    LoopFillTriangles.Add(null);
                    allOk = false; // 标记有填充失败的孔洞
                }
            }

            return allOk;
        }
    }
}